/**
 * @file filename.cpp
 * @brief nullptr关键字用于标识空指针，与NULL不同，NULL为0
 * @author Monomania (1301519350@qq.com)
 * @version 0.1
 * @date 2021-09-23
 */
#include<iostream>
#include <vector> 
#include <string>
#include <list>
#include <map>
#include <algorithm> // std::minmax_element
// #define NDEBUG
#include <assert.h>
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE true
#define FALSE false
// 定义一个不可能的数
#define INF   -99999  
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */


/**
 * 核心思想：
 * 若前一个元素大于0，则将其加到当前元素上
 * 
 * dp[i] 表表示nums中以nums[i]结尾的最大子序和
 * dp[i] = max(dp[i-1]+nums[i], nums[i]);
 * dp[i]是当前数字，要么是与前面的最大子序和的和
 */

// class Solution {
// public:
//     int maxSubArray(vector<int>& nums) {
//         int max_sum = nums[0];
//         for (int i = 1; i < nums.size(); ++i){
//             if (nums[i-1] > 0){
//                 nums[i] += nums[i-1];
//             }
//             // max_sum = max(max_sum, nums[i]);
//         }
//         auto v = max_element(nums.begin(), nums.end());
//         max_sum = *v;
//         return max_sum;
//     }
// };

// 换一个写法
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max_sum = nums[0];
        for (int i = 1; i < nums.size(); ++i){
            nums[i] = max(nums[i]+nums[i-1],nums[i]);
        }
        auto v = max_element(nums.begin(), nums.end());
        max_sum = *v;
        return max_sum;
    }
};


int main(int argc, const char** argv) {
    Solution solu = Solution();
    vector<int> nums = {-2,1,-3,4,-1,2,1,-5,4};
    
    cout << solu.maxSubArray(nums) << endl;

    return 0;
}